package com.c2b.algorithm.leetcode.base;

import java.util.ArrayDeque;
import java.util.Deque;

/**
 * <a href='https://leetcode.cn/problems/removing-stars-from-a-string/'>从字符串中移除星号(Removing Stars From a String)</a>
 * <p>给你一个包含若干星号 * 的字符串 s 。</p>
 * <p>
 * 在一步操作中，你可以：
 *     <ul>
 *         <li>选中 s 中的一个星号。</li>
 *         <li>移除星号 左侧 最近的那个 非星号 字符，并移除该星号自身。</li>
 *     </ul>
 *     返回移除 所有 星号之后的字符串。
 * </p>
 * <p>
 * <b>注意：</b>
 * <ul>
 *     <li>生成的输入保证总是可以执行题面中描述的操作。</li>
 *     <li>可以证明结果字符串是唯一的。</li>
 * </ul>
 * </p>
 * <p>
 * <b>示例：</b>
 * <pre>
 * 示例 1：
 *      输入：s = "leet**cod*e"
 *      输出："lecoe"
 *      解释：从左到右执行移除操作：
 *          - 距离第 1 个星号最近的字符是 "leet**cod*e" 中的 't' ，s 变为 "lee*cod*e" 。
 *          - 距离第 2 个星号最近的字符是 "lee*cod*e" 中的 'e' ，s 变为 "lecod*e" 。
 *          - 距离第 3 个星号最近的字符是 "lecod*e" 中的 'd' ，s 变为 "lecoe" 。
 *          不存在其他星号，返回 "lecoe" 。
 *
 * 示例 2：
 *      输入：s = "erase*****"
 *      输出：""
 *      解释：整个字符串都会被移除，所以返回空字符串。
 * </pre>
 * </p>
 *
 * <p>
 * <b>提示：</b>
 * <ul>
 *     <li>1 <= s.length <= 10^5</li>
 *     <li>s 由小写英文字母和星号 * 组成</li>
 *     <li>s 可以执行上述操作</li>
 * </ul>
 * </p>
 *
 * @author c2b
 * @since 2023/11/10 17:12
 */
public class LC2390RemovingStarsFromString_M {
    static class Solution {
        public String removeStars(String s) {
            int index = 0;
            char[] chars = s.toCharArray();
            for (int i = 0; i < chars.length; i++) {
                if (chars[i] == '*') {
                    index--;
                } else {
                    char temp = chars[index];
                    chars[index] = chars[i];
                    chars[i] = temp;
                    index++;
                }
            }
            return new String(chars, 0, index);
        }

        public String removeStars2(String s) {
            Deque<Character> characterDeque = new ArrayDeque<>();
            for (char ch : s.toCharArray()) {
                if (ch == '*') {
                    characterDeque.pollLast();
                } else {
                    characterDeque.offerLast(ch);
                }
            }
            StringBuilder res = new StringBuilder();
            while (!characterDeque.isEmpty()) {
                res.append(characterDeque.pollFirst());
            }
            return res.toString();
        }
    }

    public static void main(String[] args) {
        Solution solution = new Solution();
        System.out.println(solution.removeStars("leet**cod*e"));
        System.out.println(solution.removeStars("erase*****"));
    }
}
